1. Technical Field
The present invention relates in general to a system and method for improving software locks. More particularly, the present application relates to a system and method that reserves a software lock for threads that are waiting for the lock.
2. Description of the Related Art
In a multiprocessing environment, software locks are used to serialize access to resources. As used herein, a “thread” refers to a part of a program that can execute independently of other parts of the program. There can be multiple programs, including the operating system, operating at the same time, and each of these programs can have multiple threads. When a thread requires access to a serialized resource, a software lock is used. The software lock provides a mechanism so that one thread is able to use the resource (e.g., write to a shared memory location, etc.). While traditional locks provide a controlled means for accessing a resource, one challenge that is encountered using traditional locks is that a thread may be unintentionally starved for access to a particular resource. While this situation occurs in a multiprocessor environment, it may also occur in a uniprocessor environment under certain conditions.
FIG. 1 is a prior art depiction of a typical locking algorithm that potentially starves a process for a critical resource. In the example shown, the second thread is being starved for a particular resource. Depiction of a portion of the processing of the first thread commences at 100 and the depiction of a portion of the processing of the second thread commences at 101. At step 105, the first thread acquires a particular lock and then commences step 110 by performing work that utilizes the resource being controlled by the lock.
Sometime after the first thread has acquired the lock, but before the first thread has released the lock, the second thread requests the same software lock (step 115). At step 120, the lock manager notices that the lock is already taken (by the first thread), so, at step 125, the second thread is put to sleep and added to wait queue 130. Sometime after the second thread is put to sleep and added to the wait queue, the first thread releases the lock (step 135). The release of the lock by the first thread causes the second thread to wakeup (step 140) and the second thread is removed from wait queue 130. While the second thread is waking up, at step 145, the first thread performs work that does not require the shared resource that is being controlled by the software lock. However, before the second thread fully wakes up and requests the lock (step 160), the first thread once again needs to access the shared resource and requests the lock again at step 150. Because the lock was available and the first thread requested it before the second thread, at step 155 the first thread reacquires the lock.
Once again, the lock manager denies the lock to the second thread (step 165) because the lock has already been taken by another process (the first thread). The second thread is then put back to sleep and added to the wait queue (step 170). Unfortunately, the sequence may be repeated over and over again (step 175 and 180), thus starving the second thread so that it must wait an inordinate amount of time to acquire the shared resource being controlled by the lock. As mentioned before, while the situation described in FIG. 1 occurs in a multiprocessor environment, it may also occur in a uniprocessor environment under certain conditions. One reason that the second thread may become starved for the lock, as described above, is because the first thread is a running thread while the second thread is put to sleep. A running thread has an advantage over a sleeping thread in that it can often finish its processing and request the lock before the sleeping thread can wake up and request the lock. Using an affinity dispatcher, the second thread would be preferably dispatched to CPU 2 when it wakes up. However, if CPU 2 is busy, the second thread may be reassigned to a different CPU that is idle at the time that the second thread wakes up. Again, reassigning the second thread to an idle CPU requires additional time that provides the first thread with an additional advantage in finishing its work and re-requesting the lock.
What is needed, therefore, is a system and method that prevents one process from being starved for a shared resource. What is further needed is a system and method that reserves the lock for a waiting process so that it has a much better chance of acquiring the lock in a timely manner.